<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <!--<script src="index.js"></script>-->
    <title>连续最大子数组</title>
</head>
<body>
<script>
    var arr=[3,6,-5,-10,6,8,-1,7];


    //遍历所有的可能性，暴力破解
    function traverseAll(arr) {
        var sum=0;//数据和
        var max=0;//存储最大值
        var start=0,end=0;
        for (var i=0;i<arr.length;i++){  //起点
            sum=0;
            for (var j=i;j<arr.length;j++){ //终点
                sum+=arr[j];
                if( sum > max){
                    //发现新的最大子数组
                    max = sum;
                    start = i;
                    end = j;
                }
            }
        }
        return {
            max:max,  //最大和
            subarr:arr.slice(start,end+1) //结果子数组
        }
    }

    // console.log(traverseAll(arr));



    //分治法
   /* function divide(arr,left,right) {
        var maxleft=0,maxright=0;
        var maxleftmiddle=0,maxrightmiddle=0,leftmiddlesum=0,rightmiddlesum=0;
        var center,max=0;
        if(left==right){
            return arr[left];
        }else{
            center = Math.floor((left+right)/2) ; //中间数向下取整
            maxleft=divide(arr,left,center);//左边最大
            maxright=divide(arr,center+1,right);//右边最大

            for(var i=center;i>=left;i--){//从中间到左的最大
                leftmiddlesum+=arr[i];
                if(maxleftmiddle<leftmiddlesum){
                    maxleftmiddle = leftmiddlesum;
                }
            }

            for(var j=center+1;j<=right;j++){//从中间到右边的最大
                rightmiddlesum+=arr[j];
                if(maxrightmiddle<rightmiddlesum){
                    maxrightmiddle = rightmiddlesum;
                }
            }

            max = maxleft>maxright?maxleft:maxright;
            max = max > (maxleftmiddle+maxrightmiddle) ? max : (maxleftmiddle+maxrightmiddle);

            return max ;

        }

    }*/


    function divide(arr,left,right) {
        var maxleft=0,maxright=0;
        var maxleftmiddle=0,maxrightmiddle=0,leftmiddlesum=0,rightmiddlesum=0;
        var center,max=0;
        if(left==right){
            return{
                max:arr[left],
                start:left,
                end:left,
                subarr:arr.slice(left,left+1)
            } ;
        }else{

            center = Math.floor((left+right)/2) ; //中间数向下取整
            maxleft=divide(arr,left,center);//左边最大
            maxright=divide(arr,center+1,right);//右边最大

            var start=center,end=center;
            for(var i=center;i>=left;i--){//从中间到左的最大
                leftmiddlesum+=arr[i];
                if(maxleftmiddle<leftmiddlesum){
                    maxleftmiddle = leftmiddlesum;
                    start=i;

                }
            }

            for(var j=center+1;j<=right;j++){//从中间到右边的最大
                rightmiddlesum+=arr[j];
                if(maxrightmiddle<rightmiddlesum){
                    maxrightmiddle = rightmiddlesum;
                    end=j;

                }
            }


            if(maxleft.max>maxright.max){ // 两边比较大小
                startlr = maxleft.start;
                endlr = maxleft.end;
                max = maxleft.max;
            }else{
                startlr = maxright.start;
                endlr = maxright.end;
                max = maxright.max;
            }

            if( max < (maxleftmiddle+maxrightmiddle) ){//中间大
                max = (maxleftmiddle+maxrightmiddle);
            }else{//两边大
                start = startlr;
                end = endlr;
            }

            return {
                max:max,
                start:start,
                end:end,
                subarr:arr.slice(start,end+1)
            } ;

        }

    }

    // console.log(divide(arr,0,arr.length-1));

    function DP(arr) {

        var sum=0,max=0;
        var start=0,end=0;
        for(var i=0;i<arr.length;i++){
            sum+=arr[i];
            if( sum > max ){
                end=i;
                max = sum;
            }else if(sum<0){
                start=i+1;
                sum=0;
            }
        }
        return {
            max:max,
            start:start,
            end:end,
            subarr:arr.slice(start,end+1)
        };
    }


    console.log(traverseAll(arr));






</script>
</body>
</html>